package codingforgreat.class20;



import java.util.HashMap;

public class Class02_LargestComponentSizebyCommonFactor {


    //O(n^2)
    public static int largestComponentSize1(int[] arr){
        int N = arr.length;
        Union union = new Union(N);
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if(gbc(arr[i],arr[j]) != 1 ){
                    union.union(i,j);
                }
            }
        }
        return union.maxSize();
    }
    public static int gbc(int a,int b){
        return b == 0 ?a : gbc(b,a % b);
    }
    //O(N * V^(1/2))
    public static int largestComponentSize2(int[] arr) {
        int N = arr.length;
        Union union = new Union(N);
        //      key 某个因子   value 哪个位置拥有这个因子
        HashMap<Integer, Integer> fatorsMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int limit = (int) Math.sqrt((double) arr[i]);
            for (int j = 1; j <= limit; j++) {
                if (j != 1) {
                    if (!fatorsMap.containsKey(j)) {
                        fatorsMap.put(j, i);
                    } else {
                        union.union(fatorsMap.get(j), i);
                    }
                }
                int other = arr[i] / j;
                if (other != 1) {
                    if (!fatorsMap.containsKey(other)) {
                        fatorsMap.put(other, i);
                    } else {
                        union.union(fatorsMap.get(other), i);
                    }
                }
            }
        }
        return union.maxSize();
    }









    public static class Union{
                private int[] sizes;
                private int[] parent;
                private int[] help;

        public Union(int N) {
            sizes = new int[N];
            parent = new int[N];
            help = new int[N];
        }

        public int maxSize() {
            int ans = 0;
            for (int size : sizes) {
                ans = Math.max(ans, size);
            }
            return ans;
        }

        public int findFather(int x){
            int hi = 0;
            while(parent[x] != x){
                help[hi++] = x;
                x = parent[x];
            }
            for(int i = 0; i < hi; i++){
                parent[help[i]] = x;
            }
            return x;
        }

        public void union(int x, int y){
            int xFather = findFather(x);
            int yFather = findFather(y);
            if(xFather != yFather){
               int big = sizes[xFather] >= sizes[yFather] ?  xFather : yFather;
                int small = big == xFather ? yFather : xFather;
                parent[small] = big;
                sizes[big] += sizes[small];
            }
        }

            }
}
